package com.gule.gl.leetcode.editor.javabook;

import com.gule.gl.leetcode.editor.cn.definition.TreeNode;

import java.util.Objects;

/**
 * @Auther: gl
 * @Date: 2020/2/12 13:53
 * @Description: 找出二叉树上任意两个节点的公共父节点:findParrentRoot
 * 用后续遍历去解决问题
 * <p>
 * 衍生题目：求两个节点间的最小距离:TowNodeDistance
 * TODO 很好的题目
 */
@Deprecated
public class FindParrentRoot {

    private int count = 0;

    /**
     * 找任意两个公共的父节点
     *
     * @param root
     * @param node1
     * @param node2
     * @return
     */
    public TreeNode findParrentRoot(TreeNode root, TreeNode node1, TreeNode node2) {
        if (Objects.isNull(root) || root == node1 || root == node2) {
            return root;
        }

        TreeNode lNode = findParrentRoot(root.left, node1, node2);
        TreeNode rNode = findParrentRoot(root.right, node1, node2);

        if (Objects.isNull(lNode.left)) {
            return lNode.right;
        } else if (Objects.isNull(rNode.right)) {
            return rNode.left;
        } else {
            return root;
        }

    }

    /**
     * 任意节点到根节点的巨鹿
     *
     * @param root
     * @param node
     * @return
     */
    private int findLevel(TreeNode root, TreeNode node) {
        if (Objects.isNull(root)) {
            return -1;
        }
        if (root == node) {
            return 0;
        }
        int level = findLevel(root.left, node);
        if (level == -1) {
            level = findLevel(root.right, node);
        }
        if (level != -1) {
            return level + 1;
        }
        return -1;
    }

    /**
     * 任意两个节点的距离
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public int TowNodeDistance(TreeNode root, TreeNode p, TreeNode q) {
        if (Objects.isNull(root)) {
            return 0;
        }
        TreeNode minParrent = findParrentRoot(root, p, q);
        int disLca = findLevel(root, minParrent);
        int dis1 = findLevel(root, p);
        int dis2 = findLevel(root, q);
        return dis1 + dis2 - 2 * disLca;
    }

}
